|
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have at most three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs〔.〕 or triangulated graphs.〔. Note however that "triangulated graphs" also sometimes refers to maximal planar graphs.〕 Chordal graphs are a subset of the perfect graphs. They may be recognized in polynomial time, and several problems that are hard on other classes of graphs such as graph coloring may be solved in polynomial time when the input is chordal. The treewidth of an arbitrary graph may be characterized by the size of the cliques in the chordal graphs that contain it. ==Perfect elimination and efficient recognition== A ''perfect elimination ordering'' in a graph is an ordering of the vertices of the graph such that, for each vertex ''v'', ''v'' and the neighbors of ''v'' that occur after ''v'' in the order form a clique. A graph is chordal if and only if it has a perfect elimination ordering. (see also ) show that a perfect elimination ordering of a chordal graph may be found efficiently using an algorithm known as lexicographic breadth-first search. This algorithm maintains a partition of the vertices of the graph into a sequence of sets; initially this sequence consists of a single set with all vertices. The algorithm repeatedly chooses a vertex ''v'' from the earliest set in the sequence that contains previously unchosen vertices, and splits each set ''S'' of the sequence into two smaller subsets, the first consisting of the neighbors of ''v'' in ''S'' and the second consisting of the non-neighbors. When this splitting process has been performed for all vertices, the sequence of sets has one vertex per set, in the reverse of a perfect elimination ordering. Since both this lexicographic breadth first search process and the process of testing whether an ordering is a perfect elimination ordering can be performed in linear time, it is possible to recognize chordal graphs in linear time. The graph sandwich problem on chordal graphs is NP-complete whereas the probe graph problem on chordal graphs has polynomial-time complexity. The set of all perfect elimination orderings of a chordal graph can be modeled as the ''basic words'' of an antimatroid; use this connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chordal graph」の詳細全文を読む スポンサード リンク
|